/**
 * 生成窗口最大值
 * [4 3 5 4 3 3 6 7] 数组长度n
 * 窗口大小w
 * 随着遍历每次取w大小的窗口得到窗口下的最大值
 * ===》 队列形式 维持队首元素即 最大
 * ===》 判断下标是否过期来更新 每w个内的最大值
 *      若过期直接弹出
 * 返回这个过程中收集到的n-w+1个当前窗口最大值组成的arr
 * 
 * 复杂度：
 *      每个下标的进出都是1次，所以复杂度O(n)
 */

let arr = [4,3,5,4,3,3,6,7];// 5 5 5 4 6 7 
getMaxWindow(arr,3);
 function   getMaxWindow(arr,w){
    if(arr===null||w<1||arr.length<w){
        return null;
    }
    let queue = [];//假装是queue
    let res =  new Array(arr.length-w+1);
    let index = 0;
    for(let i in arr){
        // 如果队列的队尾元素比当前值小 直接弹出。
        while(queue.length>0&&arr[queue[queue.length-1]]<=arr[i]){
            queue.pop();
        }
        // 直至无需再弹，则直接Push 下标
        queue.push(i);
        
        // 判断是否过期
        if(queue[0] <= i-w){
            queue.shift();//删除第一个元素
        }

        if(i >= w-1){
            res[index++] = arr[queue[0]];
        }
    }
    console.log(res);
    return res;
 }